#include<bits/stdc++.h>
using namespace std;

typedef long long llong;
const int N=2e5+3;

int t,n;
int a[N];
bool c[N];
llong ans;

inline llong calc(){
    int l0=0,l1=0;
    llong ans=0;
    for(int i=1;i<=n;i++){
        if(c[i]){
            if(l1==a[i])
                ans+=a[i];
            l1=a[i];
        }
        else{
            if(l0==a[i])
                ans+=a[i];
            l0=a[i];
        }
    }
    return ans;
}

int l0[N],l1[N];

llong la;

inline void calc1(){
    llong ans=0;
    for(int i=1;i<=n;i++){
        l0[i+1]=l0[i]; l1[i+1]=l1[i];
        if(c[i]){
            if(l1[i]==a[i])
                ans+=a[i];
            l1[i+1]=a[i];
        }
        else{
            if(l0[i]==a[i])
                ans+=a[i];
            l0[i+1]=a[i];
        }
    }
    la=ans;
}

inline llong calc2(int x){
    if(c[x]){
        if(a[x]==l1[x]&&a[x]!=l0[x])
            la-=a[x];
        else if(a[x]!=l1[x]&&a[x]==l0[x])
            la+=a[x];
        int p=x+1;
        while(p<=n&&c[p]){
            l0[p]=a[x];
            p++;
        }
        if(a[p]==l0[p]&&a[p]!=a[x])
            la-=a[p];
        else if(a[p]!=l0[p]&&a[p]==a[x])
            la+=a[p];
        l0[p]=a[x];
        p=x+1;
        while(p<=n&&!c[p]){
            l1[p]=l1[x];
            p++;
        }
        if(a[p]==l1[p]&&a[p]!=l1[x])
            la-=a[p];
        else if(a[p]!=l1[p]&&a[p]==l1[x])
            la+=a[p];
        l1[p]=l1[x];
    }
    else{
        if(a[x]==l0[x]&&a[x]!=l1[x])
            la-=a[x];
        else if(a[x]!=l0[x]&&a[x]==l1[x])
            la+=a[x];
        int p=x+1;
        while(p<=n&&c[p]){
            l0[p]=l0[x];
            p++;
        }
        if(a[p]==l0[p]&&a[p]!=l0[x])
            la-=a[p];
        else if(a[p]!=l0[p]&&a[p]==l0[x])
            la+=a[p];
        l0[p]=l0[x];
        p=x+1;
        while(p<=n&&!c[p]){
            l1[p]=a[x];
            p++;
        }
        if(a[p]==l1[p]&&a[p]!=a[x])
            la-=a[p];
        else if(a[p]!=l1[p]&&a[p]==a[x])
            la+=a[p];
        l1[p]=a[x];
    }
    c[x]=!c[x];
    return la;
}

void SA(){
    calc1();
    llong maxn=0;
    for(double tmp=1e4;tmp>1e-15;tmp*=0.995){
        int x=rand()%n+1;
        llong ret=calc2(x);
        llong d=ret-maxn;
        if(d>0) ans=max(ans,maxn=ret);
        else if(exp(d/tmp)*RAND_MAX<rand()) maxn=ret;
        else calc2(x);
    }
}

void dfs(int p){
    if(p>n){
        ans=max(ans,calc());
        return;
    }
    c[p]=0;
    dfs(p+1);
    c[p]=1;
    dfs(p+1);
}

int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    ios::sync_with_stdio(0);
    srand(time(0));
    cin>>t;
    for(int q=1;q<=t;q++){
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        ans=0;
        if(n<=15){
            dfs(1);
        }
        else{
            for(int i=1;i<=n;i++)
                c[i]=i&1;
            while(1.0*clock()/CLOCKS_PER_SEC<0.95*q/t) SA();
        }
        cout<<ans<<endl;
    }
    return 0;
}